Search for: All records

The direct-sum question is a classical question that asks whether performing a task on m independent inputs is m times harder than performing it on a single input. In order to study this question, Beimel et al [BBKW14] introduced the following related problems: • The choice problem: Given m distinct instances, choose one of them and solve it. • The agreement problem: Given m distinct instances, output a solution that is correct for at least one of them. It is easy to see that these problems are no harder than performing the original task on a single instance, and it is natural to ask whether it is strictly easier or not. In particular, proving that the choice problem is not easier is necessary for proving a direct-sum theorem, and is also related to the KRW composition conjecture [KRW95]. In this note, we observe that in a variety of computational models, if f is a random function then with high probability its corresponding choice and agreement problem are not much easier than computing f on a single instance (as long as m is noticeably smaller than 2^n)